package com.adamjwh.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * 桶排序
 * 
 * @author adamjwh
 * 
 * 算法描述：
 * 设置一个定量的数组当作空桶；
 * 遍历输入数据，并且把数据一个一个放到对应的桶里去；
 * 对每个不是空的桶进行排序；
 * 从不是空的桶里把排好序的数据拼接起来。 
 *
 */
public class BucketSort {
	
	public static void bucketSort(int[] arr){
	    
	    int max = Integer.MIN_VALUE;
	    int min = Integer.MAX_VALUE;
	    for(int i = 0; i < arr.length; i++){
	        max = Math.max(max, arr[i]);
	        min = Math.min(min, arr[i]);
	    }
	    
	    //桶数
	    int bucketNum = (max - min) / arr.length + 1;
	    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
	    for(int i = 0; i < bucketNum; i++){
	        bucketArr.add(new ArrayList<Integer>());
	    }
	    
	    //将每个元素放入桶
	    for(int i = 0; i < arr.length; i++){
	        int num = (arr[i] - min) / (arr.length);
	        bucketArr.get(num).add(arr[i]);
	    }
	    
	    //对每个桶进行排序
	    int k = 0;
	    for(int i = 0; i < bucketArr.size(); i++){
	        Collections.sort(bucketArr.get(i));
	        for(int j=0; j<bucketArr.get(i).size(); j++) {
	        	arr[k++] = bucketArr.get(i).get(j);
	        }
	    }
	    
	}
	
	public static void main(String[] args) {
		int[] arr = {10,15,25,37,21,13,9,10,15,2};
		bucketSort(arr);
		System.out.println(Arrays.toString(arr));
	}

}
